home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / asm_msc1.arc / EX56.ASM < prev    next >
Encoding:
Assembly Source File  |  1988-11-20  |  2.6 KB  |  74 lines
  1. TITLE  Binary Search Procedure (EX56.ASM)
  2.           PAGE      ,132
  3. DATA      SEGMENT   PARA 'DATA'
  4. START_ADDR  DW      ?
  5. DATA      ENDS
  6. OUR_CODE  SEGMENT   PARA 'CODE'
  7.       PUBLIC    B_SEARCH
  8. B_SEARCH  PROC      FAR
  9.           ASSUME    CS:OUR_CODE,DS:DATA
  10.       PUSH      DS             ;Save caller's DS register
  11. ;
  12. ;  To start, find out if AX lies beyond the boundaries of the list.
  13. ;
  14.       CMP        AX,ES:[DI+2]     ;Search value < or = first el.?
  15.       JA        CHK_LAST         ; No.  Go check last element
  16.       LEA        SI,ES:[DI+2]     ; Yes.  Fetch addr. of first el.
  17.       JE        EXIT_1ST         ;If value = 1st element, exit
  18.       STC                 ;If value < 1st element, set CF
  19. EXIT_1ST: POP       DS             ;and then exit
  20.           RET
  21. CHK_LAST: MOV        SI,ES:[DI]         ;Point to last element
  22.       SHL        SI,1
  23.       ADD        SI,DI
  24.       CMP        AX,ES:[SI]         ;Search value > or = last el.?
  25.       JB        SEARCH           ; No.  Go search list
  26.       JE        EXIT_LAST        ; Yes.  Exit if value = last el.
  27.       STC                 ;If value > last element, set CF
  28. EXIT_LAST: POP      DS               ;   and then exit
  29.           RET
  30. ;
  31. ;  Search for value within the list.
  32. ;
  33. SEARCH:  MOV        START_ADDR,DI    ;Save starting address in memory
  34.       MOV        SI,ES:[DI]         ;Fetch index
  35. EVEN_IDX: TEST        SI,1         ;Force index to an even value
  36.       JZ        ADD_IDX
  37.       INC        SI
  38. ADD_IDX:  ADD        DI,SI         ;Calculate next search address
  39. COMPARE:  CMP        AX,ES:[DI]         ;Search value found?
  40.       JE        ALL_DONE         ; If so, exit
  41.       JA        HIGHER         ; Otherwise, find correct half
  42. ;
  43. ;  These instructions are executed if the search value is lower
  44. ;  in the list.
  45. ;
  46.       CMP        SI,2         ;Index = 2?
  47.       JNE        IDX_OK
  48. NO_MATCH: STC                 ; If so, set CF
  49.       JE        ALL_DONE         ;  and exit
  50. IDX_OK:   SHR        SI,1         ; If not, divide index by 2
  51.       TEST        SI,1         ;Force index to an even value
  52.       JZ        SUB_IDX
  53.       INC        SI
  54. SUB_IDX:  SUB        DI,SI         ;Calculate next address
  55.       JMP        SHORT COMPARE    ;Go check this element
  56. ;
  57. ;  These instructions are executed if the search value is higher
  58. ;  in the list.
  59. ;
  60. HIGHER:   CMP        SI,2         ;Index = 2?
  61.       JE        NO_MATCH         ; If so, go set CF and exit
  62.              SHR        SI,1         ; If not, divide index by 2
  63.       JMP        SHORT EVEN_IDX   ;Go check next element
  64. ;
  65. ;  Following are exit instructions.
  66. ;
  67. ALL_DONE: MOV       SI,DI         ;Move compare address into SI
  68.             MOV        DI,START_ADDR    ;Restore starting address
  69.       POP        DS
  70.            RET                 ; and exit
  71. B_SEARCH  ENDP
  72. OUR_CODE  ENDS
  73.          END       B_SEARCH
  74.